/**
 * @file     minDeleteDistance.js
 * @brief    [583. 两个字符串的删除操作](https://leetcode.cn/problems/delete-operation-for-two-strings/description/)
 * @author   Zhu
 * @date     2023-06-05 21:04
 */

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function (word1, word2) {
    // dp[i][j] = dp[i-1][j] + 1, dp[i][j-1] + 1
    // dp[0][0] = 0
    // dp[0][j] = j, dp[i][0] = i

    const m = word1.length,
        n = word2.length;

    if (m * n === 0) {
        return m || n;
    }
    const dp = [];
    for (let i = 0; i <= m; i++) {
        dp[i] = [i];
        for (let j = 1; j <= n; j++) {
            if (i == 0) {
                dp[0][j] = j;
            } else {
                if (word1[i - 1] === word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
                }
            }
        }
    }

    return dp[m][n];
};
